package es.deusto.ingenieria.aike.csp.algorithm;

import java.util.List;

import es.deusto.ingenieria.aike.csp.formulation.CSPproblem;
import es.deusto.ingenieria.aike.csp.formulation.Constraint;
import es.deusto.ingenieria.aike.csp.formulation.Variable;

/**
 * This class implements the Simple Backtracking algorithm for CSP solving. 
 * @param <Type> refers to the type of values that the CSP variables will be assigned.
 * Such a type will be specified at runtime when instantiating
 */
public class BackTracking<Type> implements CSPAlgorithm<Type> {

	private MostConstrainedVariable heuristic = new MostConstrainedVariable();
	
	public boolean solve(CSPproblem<Type> problem){				
		return this.simpleBacktracking(problem.getVariables());
	} 
	
	/**
	 * Solves the CSP by carrying out a search process where a variable is assigned a value at each step.
	 * @param variables List<Variable<Type>> containing the CSP variables.
	 * @return
	 * <ul>
	 *   <li><b>true</b> - If a complete and consistent assignment is found</li>
	 *   <li><b>true</b> - If it ends up with an incomplete assignment (some variable is left with no legal values)</li>
	 * </ul>  
	 */
	private boolean simpleBacktracking(List<Variable<Type>> variables) {
		Variable<Type> variable = getNextVariableToAssign(variables);
		
		//There is at least one variable without value.
		if (variable != null) {
			variable.resetUnassignedValues();
			return assignValue(variables, variable);
		//complete assignment (every variable has a value assigned).
		} else {			
			return true;
		}
	}
	
	/**
	 * returns an unassigned variable.
	 * @param variables List<Variable<Type>> containing the list of variables.
	 * @return Variable<Type> specifying the next variable to be assigned.
	 */
	protected Variable<Type> getNextVariableToAssign(List <Variable<Type>> variables) {		
		//return the first unassigned variable (it has no value assigned)
		int index = 0;
		int num = 10;
		int i = 0;
		boolean modified = false;
		for (;i<variables.size();i++ )
		{
			Variable<Integer> variable = (Variable<Integer>) variables.get(i);
			if (!variable.hasValue())
			{	
				if ((heuristic.calculateH(variable))< num)
				{
					index = i;
					modified = true;
				}
			}
		}
		if (modified)
		{
			Variable<Type> v = variables.get(index);
			return v;
		}
		
		//if complete assignment (i.e. every variable is assigned a value) return null
		return null;
	}
	
	/**
	 * Method to assign a value to a variable.
	 * @param variables List<Variable<Type>> containing the CSP variables.
	 * @param variable Variable<Type> specifying the variable to be assigned next
	 * @return
	 * <ul>
	 *   <li><b>true</b> - If a value can be assigned to the variable</li>
	 *   <li><b>true</b> - If a value can not be assigned to the variable</li>
	 * </ul> 
	 */
	private boolean assignValue(List<Variable<Type>> variables, Variable<Type> variable) {		
		//Flag to indicate whether the variable has been assigned
		boolean assigned = false;
		//Value to be assigned to the variable
		Type value = null;
		
		//While the variable has values that haven't been tried yet
		while (variable.hasUnassignedValues()) {			
			//get the next available value
			value = variable.getNextUnassignedValue();
			//change the flag to indicate that a value is about to be assigned
			assigned = true;			
			//For each constraint that the variable is involved in
			for (Constraint<Type> constraint: variable.getConstraints()) {
				//If the value to be assigned to the variable does NOT satisfy the constraint
				if (!constraint.isSatisfied(variable, value)){
					//change the flag back to indicate that the variable hasn't been assigned
					assigned = false;
					//break out of the for loop
					break;
				}
			}
			
			//If the value to be assigned to the variable satisfies every constraint
			if (assigned) {
				//Assign the value to the variable
				variable.setValue(value);
				//Make an indirect recursive call to the method simpleBacktracking() to
				//assign values to the rest of the CSP variables
				assigned = this.simpleBacktracking(variables);
				//On completing the recursion, a true value indicates that the variable assignment
				//just made before the recursive call lead to a correct solution...
				if (assigned) {
					//... and so we break out of the while loop since there is no need
					// to try other values for the variable
					break;					
					//On completing the recursion, a false value indicates that the variable assignment
					//just made before the recursive call lead to an incorrect solution...
				} else {
					//... and so we remove the value assigned to the variable 
					// and continue within the while loop to try other values for the variable
					variable.resetValue();
				}	
			}			
		}
		
		//The method returns the flag that indicates whether a value has been 
		//assigned to the selected variable.
		return assigned;
	}
}